// n choose k?


const N = 4

const fourSum = function (nums: number[], target: number) {

    let ans: number[][] = []
    let container: number[] = []

    nums.sort((a, b) => a - b)


    const equal = (a: any[], b: any[]) => a.every((item, index) => b[index] === item)

    function sum(a: number[]): number {

        if (a.length === 0) return Number.MIN_SAFE_INTEGER

        return a.reduce((s, a) => s + a, 0)
    }

    const biSearch = (from: number, target: number) => {
        let beg = from, end = nums.length - 1

        while (beg <= end) {
            const mid = Math.floor((beg + end) / 2)

            if (nums[mid] === target) {
                return mid
            }

            if (nums[mid] > target) {
                end = mid - 1
            } else {
                beg = mid + 1
            }
        }
        return -1
    }

    function search(from: number) {

        // console.log(container)

        if (container.length === N) {
            if (sum(container) === target) {

                if (ans.every(a => !equal(a, container)))
                    ans.push(container.slice())
                return
            }
        }

        if (sum(container) > target && nums[from] > 0) {
            return
        }


        if (from >= nums.length) {
            return
        }


        if (container.length === N - 1) {

            const next = biSearch(from, target - sum(container))

            if (next >= from) {

                container.push(nums[next])
                search(next + 1)
                container.pop()
            }
            return
        }

        container.push(nums[from])
        search(from + 1)

        container.pop()
        let next = from + 1
        for (; next < nums.length; next++) {
            if (nums[next] !== nums[from])
                break
        }

        search(next)
    }

    search(0)

    // console.log(ans)
    // console.log(nums)
    return ans
};


fourSum([0,0,0,0,0,0],
    0)
// console.log(threeSumClosest([-1, 2, 1, 4], 1));